package com.liuyfly.leetcode.questions;

/**
 * @author liuyangfang 2021/9/27 下午8:13
 */
public class Question0035 {

    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为
     * O(log n) 的算法。 <br/>
     * <br/>
     * 链接：https://leetcode.cn/problems/search-insert-position
     */
    public static int searchInsert(int[] nums, int target) {
        return searchInsert(nums, 0, nums.length - 1, target);
    }

    public static int searchInsert(int[] nums, int start, int end, int target) {
        int middle = (start + end) / 2;
        if (nums[middle] == target) {
            return middle;
        }
        if (nums[middle] > target) {
            if (middle - 1 > 0) {
                return searchInsert(nums, 0, middle - 1, target);
            } else {
                if (nums[0] >= target) {
                    return 0;
                } else {
                    return 1;
                }
            }
        }
        if (nums[middle] < target) {
            if (middle + 1 < end) {
                return searchInsert(nums, middle + 1, end, target);
            } else {
                if (nums[end] < target) {
                    return end + 1;
                } else {
                    return end;
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] nums = { 1, 3 };
        int target = 3;
        int result = searchInsert(nums, target);
        System.out.println(result);
    }
}
